/*
 * Copyright 2010 - 2011, The PLDesktop Development Team
 *
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Lesser General Public
 *  License as published by the Free Software Foundation; either
 *  version 2.1 of the License, or (at your option) any later version.
 *
 *  This library is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 *  Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public
 *  License along with this library; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 *
 */

#include <tools/PLRadixTreeVoid.h>

#include <tools/PLRadixTree.h>

using namespace PLSDK;

const uint8_t nullKey[] = {0};

PLRadixTree<void*>::PLRadixTree() : m_nItems(0), m_pRoot(0) {}

PLRadixTree<void*>::~PLRadixTree() {
    clear();
}

PLRadixTree<void*>::PLRadixTree(const PLRadixTree &x) : m_nItems(0), m_pRoot(0) {
    clear();
    delete m_pRoot;
    m_pRoot = cloneNode(x.m_pRoot, 0);
    m_nItems = x.m_nItems;
}

PLRadixTree<void*> &PLRadixTree<void*>::operator =(const PLRadixTree &x) {
    clear();
    delete m_pRoot;
    m_pRoot = cloneNode(x.m_pRoot, 0);
    m_nItems = x.m_nItems;
    return *this;
}

size_t PLRadixTree<void*>::count() const {
    return m_nItems;
}

void PLRadixTree<void*>::insert(const char *key, void *value) {
    if(!m_pRoot) {
        // The root node always exists and is a lambda transition node (zero-length
        // key). This removes the need for most special cases.
        m_pRoot = new PLRadixTreeNode();
        m_pRoot->setKey(nullKey);
    }
    PLRadixTreeNode *pNode = m_pRoot;
    const uint8_t *cpKey = reinterpret_cast<const uint8_t *>(key);
    while(true) {
        switch(pNode->matchKey(cpKey)) {
            case PLRadixTreeNode::ExactMatch: {
                pNode->setValue(value);
                return;
            }
            case PLRadixTreeNode::NoMatch: {
                printf("RadixTree: Algorithmic error (insert)");
                abort();
                break;
            }
            case PLRadixTreeNode::PartialMatch: {
                // We need to create an intermediate node that contains the 
                // partial match, then adjust the key of this node.
                // Find the common key prefix.
                size_t i = 0;
                while (cpKey[i] == pNode->m_pKey[i]) {
                    i++;
                }
                PLRadixTreeNode *pInter = new PLRadixTreeNode();
                // Intermediate node's key is the common prefix of both keys.
                pInter->m_pKey = new uint8_t[i + 1];
                memcpy(pInter->m_pKey, cpKey, i);
                pInter->m_pKey[i] = 0;
                // Must do this before pNode's key is changed.
                pNode->getParent()->replaceChild(pNode, pInter);
                // pNode's new key is the uncommon postfix.
                size_t len = 0;
                while(pNode->m_pKey[len]) {
                    len++;
                }
                uint8_t *pTmpKey = new uint8_t[(len - i) + 1];
                memcpy(pTmpKey, &pNode->m_pKey[i], len - i);
                pTmpKey[len-i] = 0;
                delete[] pNode->m_pKey;
                pNode->m_pKey = pTmpKey;
                // If the uncommon postfix of the key is non-zero length, we have
                // to create another node, a child of pInter.
                if(cpKey[i] != 0) {
                    PLRadixTreeNode *pChild = new PLRadixTreeNode();
                    pChild->setKey(&cpKey[i]);
                    pChild->setValue(value);
                    pChild->setParent(pInter);
                    pInter->addChild(pChild);
                } else {
                    pInter->setValue(value);
                }
                pInter->setParent(pNode->getParent());
                pInter->addChild(pNode);
                pNode->setParent(pInter);
                m_nItems++;
                return;
            }
            case PLRadixTreeNode::OverMatch: {
                size_t i = 0;
                if(pNode->m_pKey) {
                    while(pNode->m_pKey[i++]) {
                        cpKey++;
                    }
                }
                PLRadixTreeNode *pChild = pNode->findChild(cpKey);
                if(pChild) {
                    pNode = pChild;
                    // Iterative case.
                    break;
                } else {
                    // No child - create a new one.
                    pChild = new PLRadixTreeNode();
                    pChild->setKey(cpKey);
                    pChild->setValue(value);
                    pChild->setParent(pNode);
                    pNode->addChild(pChild);
                    m_nItems++;
                    return;
                }
            }
        }
    }
}

void *PLRadixTree<void*>::lookup(const char *key) {
    if(!m_pRoot) {
        // The root node always exists and is a lambda transition node (zero-length
        // key). This removes the need for most special cases.
        m_pRoot = new PLRadixTreeNode();
        m_pRoot->setKey(nullKey);
    }
    PLRadixTreeNode *pNode = m_pRoot;
    const uint8_t *cpKey = reinterpret_cast<const uint8_t*>(key);
    while(true) {
        switch(pNode->matchKey(cpKey)) {
            case PLRadixTreeNode::ExactMatch:
                return pNode->getValue();
            case PLRadixTreeNode::NoMatch:
            case PLRadixTreeNode::PartialMatch:
                return 0;
            case PLRadixTreeNode::OverMatch: {
                size_t i = 0;
                while(pNode->m_pKey[i++]) {
                    cpKey++;
                }
                PLRadixTreeNode *pChild = pNode->findChild(cpKey);
                if(pChild) {
                    pNode = pChild;
                    // Iterative case.
                    break;
                } else {
                    return 0;
                }
            }
        }
    }
}

void PLRadixTree<void*>::remove(const char *key) {
    if(!m_pRoot) {
        // The root node always exists and is a lambda transition node (zero-length
        // key). This removes the need for most special cases.
        m_pRoot = new PLRadixTreeNode();
        m_pRoot->setKey(nullKey);
    }
    PLRadixTreeNode *pNode = m_pRoot;
    const uint8_t *cpKey = reinterpret_cast<const uint8_t*>(key);
    // Our invariant is that the root node always exists. Therefore we must
    // special case here so it doesn't get deleted.
    if(*cpKey == 0) {
        m_pRoot->setValue(0);
        return;
    }
    while(true) {
        switch(pNode->matchKey(cpKey)) {
            case PLRadixTreeNode::ExactMatch: {
                // Delete this node. If we set the value to zero, it is effectively removed from the map.
                // There are only certain cases in which we can delete the node completely, however.
                pNode->setValue(0);
                m_nItems--;
                // We have the invariant that the tree is always optimised. This means that when we delete a node
                // we only have to optimise the local branch. There are two situations that need covering:
                //   (a) No children. This means it's a leaf node and can be deleted. We then need to consider its parent,
                //       which, if its value is zero and now has zero or one children can be optimised itself.
                //   (b) One child. This is a linear progression and the child node's key can be changed to be concatenation of
                //       pNode's and its. This doesn't affect anything farther up the tree and so no recursion is needed.
                PLRadixTreeNode *pParent = 0;
                if(pNode->m_nChildren == 0) {
                    // Leaf node, can just delete.
                    pParent = pNode->getParent();
                    pParent->removeChild(pNode);
                    delete pNode;
                    pNode = pParent;
                    // Optimise up the tree.
                    while(true) {
                        if(pNode == m_pRoot) {
                            return;
                        }
                        if(pNode->m_nChildren == 1 && pNode->getValue() == 0) {
                            // Break out of this loop and get caught in the next
                            // if(pNode->m_nChildren == 1)
                            break;
                        }
                        if(pNode->m_nChildren == 0 && pNode->getValue() == 0) {
                            // Leaf node, can just delete.
                            pParent = pNode->getParent();
                            pParent->removeChild(pNode);
                            delete pNode;
                            pNode = pParent;
                            continue;
                        }
                        return;
                    }
                }
                if(pNode->m_nChildren == 1) {
                    // Change the child's key to be the concatenation of ours and 
                    // its.
                    PLRadixTreeNode *pChild = pNode->getFirstChild();
                    pParent = pNode->getParent();
                    // Must call this before delete, so pChild doesn't get deleted.
                    pNode->removeChild(pChild);
                    pChild->prependKey(pNode->getKey());
                    pChild->setParent(pParent);
                    pParent->removeChild(pNode);
                    pParent->addChild(pChild);
                    delete pNode;
                }
                return;
            }
            case PLRadixTreeNode::NoMatch:
            case PLRadixTreeNode::PartialMatch:
                // Can't happen unless the key didn't actually exist.
                return;
            case PLRadixTreeNode::OverMatch: {
                size_t i = 0;
                if(pNode->m_pKey) {
                    while(pNode->m_pKey[i++]) {
                        cpKey++;
                    }
                }
                PLRadixTreeNode *pChild = pNode->findChild(cpKey);
                if(pChild) {
                    pNode = pChild;
                    // Iterative case.
                    break;
                } else {
                    return;
                }
            }
        }
    }
}

PLRadixTreeNode *PLRadixTree<void*>::cloneNode(PLRadixTreeNode *pNode, PLRadixTreeNode *pParent) {
    // Deal with the easy case first.
    if(!pNode) {
        return 0;
    }
    PLRadixTreeNode *n = new PLRadixTreeNode();
    n->setKey(pNode->m_pKey);
    n->setValue(pNode->value);
    n->setParent(pParent);
    for(size_t i = 0; i < 16; i++) {
        if(pNode->m_pChildren[i] == 0) {
            continue;
        }
        for(size_t j = 0; j < 16; j++) {
            if(pNode->m_pChildren[i]->p[j] == 0) {
                continue;
            }
            n->addChild(cloneNode(pNode->m_pChildren[i]->p[j], n));
        }
    }
    return n;
}

void PLRadixTree<void*>::clear() {
    delete m_pRoot;
    m_pRoot = new PLRadixTreeNode();
    m_pRoot->setKey(nullKey);
    m_nItems = 0;
}

template class PLRadixTree<void*>;
